package com.maiikun.hash_demo;

import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Objects;

public class MyHashMap<K, V> {

    private Node<K, V>[] tab = new Node[16];

    private int size = 0;

    private final double RATE = 0.75;

    /**
     * map的新增方法 - 若key已经存在则会返回旧值
     *
     * @param key
     * @param val
     * @return
     */
    public V put(K key, V val) {
        int index = indexOf(key);
        Node<K, V> head = tab[index];
        if (head == null) {
            tab[index] = new Node<>(key, val);
            size++;
            resizeIfNecessary();
            return null;
        }

        // 拉链法
        while (true) {
            if (head.key.equals(key)) {
                // 已经有key对应的val了 修改值后将旧值返回
                V oldVal = head.val;
                head.val = val;
                return oldVal;
            }
            if (head.next == null) {
                head.next = new Node<>(key, val);
                size++;
                resizeIfNecessary();
                return null;
            }
            head = head.next;
        }
    }

    public V get(K key) {
        int index = indexOf(key);
        Node<K, V> head = tab[index];
        if (head == null) return null;

        while (true) {
            if (head.key.equals(key)) {
                return head.val;
            }
            head = head.next;
            if (head == null) return null;
        }
    }

    public V remove(K key) {
        int index = indexOf(key);
        Node<K, V> head = tab[index];
        if (head == null) return null;

        while (true) {
            if (head.key.equals(key)) {
                Node<K, V> removeNode = tab[index];
                tab[index] = null;
                size--;
                return removeNode.val;
            }
            head = head.next;
            if (head == null) return null;
        }
    }

    /**
     * 头插法
     */
    private void resizeIfNecessary() {
        if (size < tab.length * RATE) {
            return;
        }
        int newSize = tab.length << 1;

        Node<K, V>[] newTab = new Node[newSize];
        for (Node<K, V> curNode : tab) {
            // 如果有链表要进行拷贝
            while (curNode != null) {
                int newIndex = curNode.key.hashCode() & (newTab.length - 1);
                Node<K, V> head = newTab[newIndex];
                if (head == null) {
                    // 不存在哈希冲突
                    newTab[newIndex] = new Node<>(curNode.key, curNode.val);
                } else {
                    // 发送哈希冲突 拉链法
                    Node<K, V> newNode = new Node<>(curNode.key, curNode.val);
                    newNode.next = head;
                    newTab[newIndex] = newNode;
                }
                curNode = curNode.next;
            }
        }
        tab = newTab;
    }

    /**
     * 尾插入法 - 防止多线程条件下的扩容循环链表问题
     * <p>
     * 但是我认为本来HashMap就是线程不安全的 - 尾插法的时间复杂度还比较高
     */
    private void resizeIfNecessaryWithTail() {
        if (tab == null || tab.length == 0 || size < tab.length * RATE) {
            return;
        }

        int newSize = tab.length << 1; // 扩容为原来的两倍
        Node<K, V>[] newTab = new Node[newSize];

        for (Node<K, V> currentNode : tab) {
            while (currentNode != null) {
                int newIndex = currentNode.key.hashCode() & (newTab.length - 1);
                Node<K, V> existingHead = newTab[newIndex];

                if (existingHead == null) {
                    // 如果新索引位置为空，直接插入新节点
                    newTab[newIndex] = new Node<>(currentNode.key, currentNode.val);
                } else {
                    // 发生哈希冲突，使用拉链法插入链表尾部
                    Node<K, V> tail = existingHead;
                    while (tail.next != null) {
                        tail = tail.next;
                    }
                    tail.next = new Node<>(currentNode.key, currentNode.val);
                }

                currentNode = currentNode.next;
            }
        }

        tab = newTab; // 更新引用
    }


    public int size() {
        return size;
    }

    /**
     * 获取要Hash到数组的下标
     * <p>
     * 为什么要这样设计呢？ 位运算比较快
     * 因为比如8的二进制为 1000 那么我们按位与的话一定是小于8的 - 但是缺陷也很明显,那就是只有8
     * 所以我们就要保证说他是全1的这样的话就可以覆盖到0 - x的范围了
     * 这样就需要保证size的大小为 2^x
     * <p>
     * 引入扰乱函数
     *
     * @param key
     * @return
     */

    public int indexOf(K key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

    static class Node<K, V> implements Entry<K, V> {
        K key;
        V val;

        Node<K, V> next;

        public Node() {
        }

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
            next = null;
        }

        public final K getKey() {
            return key;
        }

        public final V getValue() {
            return val;
        }

        @Override
        public final V setValue(V newValue) {
            V oldValue = val;
            val = newValue;
            return oldValue;
        }

        public final String toString() {
            return key + "=" + val;
        }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(val);
        }
    }



    public interface Entry<K, V> {

        K getKey();

        V getValue();

        V setValue(V value);
    }

}

